// 650. 只有两个键的键盘


//* 递归five解法
function minSteps(n: number): number {
    if(n==1) return 0
    const maxOfN = getMaxPart(n)
    const times = n / maxOfN
    return minSteps(maxOfN) + times
};

//获取不包括自身的最大因子
function getMaxPart(n:number):number{
    let max = 1
    for(let i=2;i<=n/2;i++){
        if(!(n%i)){
            max = i
        }
    }
    return max
}


//! 迭代解法
//! 递归解法是从后往前，改为对应的迭代版本依旧是从后往前，比较慢，这个直接从前往后
// class Solution {
//     public int minSteps(int n) {
//         int ans = 0, d = 2;
//         while (n > 1) {
//             while (n % d == 0) {
//                 ans += d;
//                 n /= d;
//             }
//             d++;
//         }
//         return ans;
//     }
// }

